This invention relates to a method and apparatus for extracting reliability information from partial response channels, and more particularly, to the extraction of soft information from partial response channels by using a dominant error event list.
Digital transmission and recording systems convey discrete-time data sequences across channels using signals which are variable in nature. A primary goal of any such system is to convey information at the fastest possible rate with a minimum number of errors. Accordingly, numerous approaches for error control have been developed to try to minimize and/or correct errors in transmitted signals, as illustrated in U.S. Pat. No. 6,029,264 to Kobayashi et al.; and xe2x80x9cError Control Coding, Fundamentals and Applications,xe2x80x9d by S. Lin and D. Costello, Jr., Pages 1-14, Prentice Hall, 1983; both of which are incorporated herein fully by reference.
A data sequence having a bit interval T and comprising, for example, a series of bits which change in amplitude (e.g., a change from a positive-amplitude bit +A to a negative-amplitude bit xe2x88x92A or vice versa) and/or which remain unchanged (e.g., no change in state of a data bit from one pulse to the next) with the occurrence of each bit interval T is transmitted as a sequence of analog pulses each of a certain duration equal to the bit interval T. FIG. 1 illustrates an example of an input data sequence 1, 1, xe2x88x921 (identified respectively as pulses 102, 104, and 106) and the corresponding transmitted output sequence, identified by the dotted line 210. In this example, a xe2x80x9c1xe2x80x9d indicates a positive-amplitude bit +A and a xe2x80x9cxe2x88x921xe2x80x9d indicates a negative-amplitude pulse xe2x88x92A. As can be seen in FIG. 1, the pulses of the transmitted output sequence have rounded edges as compared to the square edges of the input data sequence 102, 104, and 106.
Despite the somewhat imprecise correlation between the input data sequence 102, 104, 106 and the transmitted output data sequence 210 of FIG. 1, the different pulses are distinguishable from each other nonetheless, using a well-known technique referred to as xe2x80x9csequence detection.xe2x80x9d Even if the signal is corrupted by noise, the detection of each bit is accomplished by sampling and storing the value of each bit at the point P in time, corresponding to the peak value X of the transmitted signal. The bit being sampled at a time P(n) is referred to herein as the xe2x80x9cpresent is samplexe2x80x9d or xe2x80x9cpresent bit.xe2x80x9d By comparing the value of the present sample with the value of the samples immediately preceding the present sample in the data sequence (e.g., the samples taken at time P(nxe2x88x921), P(nxe2x88x922), P(nxe2x88x923), . . . P(nxe2x88x92M+1), where M is the channel memory, i.e., the number of previous samples that influence the present sample) it can be determined if a change in amplitude has occurred. When the present sample is being compared or is otherwise under scrutiny, it is also known as the xe2x80x9cbit of interest.xe2x80x9d
Although sequence detection offers a reasonable method of error control, a problem occurs when the overall data rate is increased, since the bit intervals T overlap as the total time t is shortened to accommodate the additional data to be transmitted. FIG. 2 illustrates a situation in which the data rate for the data sequence of FIG. 1 is increased. As shown in FIG. 2, a second bit 204 is transmitted before the transmission of first bit 202 has been completed. Since the bits overlap, the combined pulse, obtained by superposition of the overlapping pulses, results in a wave shape that does not allow the first pulse and the second pulse to be easily distinguished from each other. The combined pulse wave form is identified in FIG. 2 as dotted line 210.
This complicated wave form 210 is created because the present sample sampled at time n at the peak value X contains not only the value of pulse 204 at time n but also includes the xe2x80x9ctailxe2x80x9d of previous pulse 202. This effect is known as inter-symbol interference, or ISI. Base-band communication systems transmit data at a high rate (e.g. 1000 Mb/s) in comparison to data transmission using the channel frequency band (e.g. 500 MHz). This high rate of data transmission can result in severe ISI.
If the pulses have short tails, the ISI is limited, since at some time interval (i.e., at the point at which the prior pulse has been completely transmitted) a previous pulse will no longer affect the value of the present sample. From the standpoint of detection, it is desirable that the samples of the signal tail be limited to a finite number of integer values to reduce the number of comparisons that must be made. Systems utilizing this property are called xe2x80x9cpartial responsexe2x80x9d (PR) systems. Examples of such systems are described in, for example, xe2x80x9cModulation and Coding for Information Storagexe2x80x9d by P. Siegel and J. Wolf, IEEE Communications Magazine, pp. 68-89, December 1991; and xe2x80x9cApplication of Partial Response Channel Coding to Magnetic Recording Systems,xe2x80x9d by H. Kobayashi and D. Tang, IBM J. Res. and Dev, vol. 14, pp. 368-375, July 1997, both of which are incorporated fully herein by reference.
The above-mentioned sequence detection technique is commonly used to detect the presence of ISI in a sampled signal. According to this technique, a sequence detector is employed to detect and identify transmitted (or, in the case of magnetic recording, recorded) sequences of pulses which are more likely to be incorrectly transmitted, using knowledge of noise statistics and knowledge of the channel configuration (e.g., the dependence of noise samples on previous noise samples; noise power; and/or partial response polynomials). A common noise model is called Additive White Gaussian Noise (AWGN), and a common channel model is linear time-invariant channel.
A maximum-likelihood sequence detector (MLSD) is a known sequence detector used for an uncoded, linear ISI channel (a channel which is transmitting pulses that are close together and thus having pulses which interfere with each other) with additive Gaussian noise. An example of an MLSD is described in an article entitled xe2x80x9cMaximum Likelihood Sequence Detection in the Presence of Intersymbol Interferencexe2x80x9d by G. D. Forney (IEEE Trans. Inform. Theory, Vol. IT-25, pp. 332-335, May 1979), incorporated fully herein by reference.
A MLSD comprises a whitened matched filter (WMF), having an output that is sampled at the pulse rate of the input signal. The sampled output is input to a Viterbi detector having a trellis structure which reflects the data sequence transmitted over the ISI channel and detects the data. MLSD is not practical, particularly for communication and recording systems, because the structure of the MLSD is prohibitively complex to implement, requiring an unlimited number of states in the Viterbi detector, i.e., the hardware required to implement it is very complex.
PR systems utilize equalization to deal with ISI-related errors. Equalization is the process of reducing distortion over transmission paths by inserting compensation devices, e.g., amplifiers, in the transmission path. Placing an equalizer on the front end of a receiver receiving the transmitted data sequence allows ISI to be reduced and controlled, or even eliminated altogether. A detailed explanation of equalization is provided in the previously-cited article by P. Siegel and J. Wolf.
Complete elimination of ISI using equalization can be accomplished only in older, less sophisticated recording channel systems with low data rates, or in recording systems having low recording densities where the pulses are far enough apart to avoid ISI. In PR systems, a data sequence is reconstructed from a suitably equalized received (readback) signal, without whitened filtering, using a Viterbi detector. The noiseless equalizer output sample resulting from the use of this approach is affected by only a finite number of previous input (transmitted or recorded) samples; thus, the set of equalizer output values has set boundaries.
The well-known Viterbi algorithm used by Viterbi detectors is relatively simple, making it a good choice for use in an uncoded communication system where soft-output (i.e., reliability-checking) is not required. However, in many applications, the data transmitted over channels is encoded to improve the overall error performance of the system. Soft-output is required in (a) concatenated systems having a pair of codes (inner and outer code), wherein the inner code generates soft outputs to improve the performance of the outer code, and (b) iterative decoding schemes where a decoder xe2x80x9cpurifiesxe2x80x9d its decisions about certain code symbols through a series of operations performed on a whole codeword (i.e., after each iteration there are less errors in the code word).
One of the most commonly-used algorithms for sequence detection is Hagenauer""s soft-output-Viterbi-algorithm (SOVA) used in concatenation with some outer code such as a Reed Solomon code. The soft output at a particular time instant, produced by SOVA, is determined on the basis of the Euclidean distance between the two xe2x80x9cbestxe2x80x9d paths that merge to the same state. This merging of states is based on the well-known concept of xe2x80x9cchannel trellis.xe2x80x9d Trellis describes all possible data sequences that can occur at the output of the channel as a result of the input. The state of the trellis is defined by certain of the channel outputs, and the path through the trellis is called the output sequence. Two paths are considered to be merged if the corresponding output sequences are different when they are input but at some point become the same.
The merged paths are then compared and a smaller level of reliability (i.e., a lower level of confidence in the accuracy of the data sequence being considered) is assigned to bits that do not agree. The procedure is repeated for all channel (or trellis) states. The VA decision on a particular bit together with its reliability level is referred to as soft output or soft information. According to the SOVA method of the prior art, the comparison procedure must be performed for all possible merged path pairs, and for all states, or equivalently for all possible error event sequences.
FIG. 3 is a block diagram depicting a prior-art PR channel system comprising an encoder 310, a partial response channel 320, a Viterbi detector 330, and a decoder 340. Only the digital portion of the transmission system is illustrated; modulators, demodulators, filters and all other analog blocks are not the focus of this invention and are thus omitted from FIG. 3.
In the system of FIG. 3, encoder 310 translates a data sequence {a(k)} to a sequence {d(k)} in such a way that sequence {a(k)} can be uniquely reconstructed from sequence {d(k)} to minimize transmission errors. This can be accomplished, for example, by adding parity bits to make sure that the code words cannot be confused with each other. In a known manner using control codes, sequence {a(k)} can be reconstructed even when some symbols of the translated sequence {d(k)} are corrupted by errors during the transmission of the signal to encoder 310. For the purpose of explanation it is assumed that the a(k) data sequence is binary e.g., (a(k))xcex5{0,1}, where a xe2x80x9c0xe2x80x9d is an indication of a negative pulse and a xe2x80x9c1xe2x80x9d is indicative of a positive pulse. Typically, decoder 340 will use estimates of transmitted data x(k) (called hard decisions) output from Viterbi detector 330 to correct errors; however, some types of decoders, such as an iterative decoder, can improve decoding performances using soft decisions instead of hard decisions. This means that instead of using only the output x(k) (also called the xe2x80x9cViterbi estimatexe2x80x9d or xe2x80x9cViterbi decisionxe2x80x9d) from the Viterbi detector 330, decoder 340 also requires knowledge of the reliability of the specific value of x(k). The Viterbi estimate x(k) together with its reliability creates a soft decision.
Due to noise and other disturbances, the Viterbi estimate {x(k)} of the transmitted stream and the transmitted stream itself {d(k)} often differ. Their difference is called an error sequence {xcex5(k)}, where {xcex5(k)}=x(k)xe2x88x92d(k). For good channels, i.e., channels with low noise power and which have a small number of errors, the error sequence is zero almost everywhere, but when the error sequence is nonzero, it can be observed that some error patterns occur much more often than others. Although any error pattern is possible, these more frequent error patterns dominate overall system performance. A recognition and explanation of the phenomenon of recurring error sequences, which is inherent for all PR systems, can be found in xe2x80x9cMaximum Likelihood Sequence Estimators: a Geometric Viewxe2x80x9d by L. Barbosa, IEEE Trans. Inform. Theory, vol. It-35, pp. 419-427, March 1989, incorporated fully herein by reference. Simply described, the Euclidean distance from channel output sequences corresponding to a sequence {d(k)} to the channel output sequence corresponding to {d(k)xe2x88x92xcex5(k)}, where {xcex5(k)} is one of the dominant (more frequently occurring) error sequences, will always be smaller than the distance to any other error sequence, and this is why the Viterbi detector (which in fact uses Eucledian metric) confuses them. This is also why dominant error patterns are called minimum distance error event sequences.
A method of finding dominant error event sequences is described in xe2x80x9cError-Event Characterization on Partial-Response Channelsxe2x80x9d by S. Altekar. M. Berggren, B. Moision, P. Siegel, and J. Wolf, IEEE Trans. Inform. Theory, vol. 45, no. 1, pp. 241-247, Jan. 1999, incorporated fully herein by reference. In recording systems, for a given partial response polynomial, the set of dominant error event sequences depends also on the channel bit density (e.g., the number of pulses transmitted per bit interval) because of noise coloration due to equalization. Other methods for determining dominant error event sequences are also known. See, for example, xe2x80x9cApplication of Partial Response Channel Coding to Magnetic Recording Systemsxe2x80x9d by H. Kobayashi and D. Tang, IBM J. Res. And Dev., vol. 14, pp. 368-375, July 1979 and xe2x80x9cFinite-state Modulation Codes for Data Storagexe2x80x9d by B. Marcus, P. Siegel, and J. Wolf, IEEE Journal on Select. Areas in Commun., vol. 10, no. 1, pp5-37, January 1992, both of which are fully incorporated herein by reference. However, as noted above, prior art systems require that each sample in a data sequence (e.g., all samples taken previously at times P(nxe2x88x921), P(nxe2x88x922), . . . , P(nxe2x88x92Smin) as well as all samples to be taken in the future at times P(n+1), P(n+2), . . . , P(n+Smax) be considered when evaluating the accuracy of the present sample taken at time P(n). This results in a slow and complex procedure and requires large amounts of memory to store each and every sample.
Thus, while it is known that certain error event sequences occur more frequently than others, it would be desirable to have a method and system for generating soft outputs which can quickly and simply determine the accuracy of a sampled data sequence and which can accomplish these goals with a minimum storage requirement.
The present invention is a method of generating soft outputs by taking advantage of the fact that, in PR channels, there exists a set of error event sequences that occur more often than others. This results in a soft output extractor with significantly lower complexity than the prior art SOVA system. Minimum distance error event sequences are identified and soft information or bit reliabilities of the error event bits making up the error event sequences (as contrasted to reliabilities of the overall error event sequence) are extracted from the PR channel based on the identified sequences. The soft information is then used by an iterative error control decoder to correct errors more efficiently.
In contrast to SOVA where soft information is generated by a modified Viterbi detector, in the present invention the soft information extraction takes place after the Viterbi detector. The present invention calculates the likelihood of the occurrence of error event sequences and converts the error event likelihoods to bit likelihood ratios. A xe2x80x9cbit likelihood ratioxe2x80x9d is defined as the ratio of (a) the probability that a certain bit is transmitted correctly (i.e., is the same before and after the Viterbi detector) and (b) the probability that it was not transmitted correctly.
One aspect of the present is a method of extracting reliability information for a bit of interest in a group of bits comprising a data sequence on a partial response channel, comprising the steps of (a) calculating error event likelihoods with respect to a data sequence on said partial response channel; and (b) deriving a bit likelihood ratio for the bit of interest from said error event likelihood values The present invention may be embodied in an algorithm for generating soft outputs for PR channels by using a property of PR channels that there exists a set of error event sequences that occur more often than others.
In another embodiment, the calculating step includes atleast the steps of: compiling a first error event set comprising error event sequences; selecting, from the first error event set, a second error event set comprising error event sequences which affect the bit of interest; and determining the error event likelihood value of each error event sequence of the second error event set.
In a further embodiment, the deriving step includes at least the steps of: determining which of the error event likelihood values indicates an error event having the highest probability of occurring; and assigning to the bit of interest a bit likelihood value corresponding to the error event likelihood value for the error event determined to have the highest probability of occurring.
In yet another embodiment, the error event sequences each comprise one or more error event bits, with each error event bit having a bit likelihood value, and the method further includes the steps of: determining the bit likelihood value of each error event bit associated with a particular error event sequence in the second error event set; and changing the bit likelihood value of each error event bit having a bit likelihood value greater than the error event likelihood value of its associated error event sequence, to equal the error event likelihood value of its associated error event sequence.